package Search;

public class BlockSearch {
    //分块查找
    public static void main(String[] args) {
        //核心：块内无序，块间有序
        int[] arr={16,5,9,12,21,18,
                    32,23,37,26,45,34,
                    50,48,61,52,73,66};
        int k=38;
        //1.分块（建立索引表）
        Block b1=new Block(21,0,5);
        Block b2=new Block(45,6,11);
        Block b3=new Block(73,12,17);

        Block[] block={b1,b2,b3};


        //2.确定所在的块内的索引
        int index=getindex(block,arr,k);
        System.out.println(index);

    }

    private static int getindex(Block[] block, int[] arr, int k) {
        //确定所在的块
        int b=getblock(block,k);
        if(b==-1){
            return -1;
        }
        for(int i=block[b].getStart();i<block[b].getEnd();i++){
            if(arr[i]==k){
                return i;
            }
        }
        return -1;
    }

    private static int getblock(Block[] block, int k) {
        for (int i = 0; i < block.length; i++) {
            if(block[i].getMax()>=k){
                return i;
            }
        }
        return -1;

    }


    public static class Block{
        private int max;
        private int start;
        private int end;

        public Block(int max, int start, int end) {
            this.max = max;
            this.start = start;
            this.end = end;
        }

        public int getMax() {
            return max;
        }

        public void setMax(int max) {
            this.max = max;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }
    }
}
